package com.mj;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.mj.BinarySearchTree.Visitor;
import com.mj.printer.BinaryTreeInfo;

public class BinaryTree<E> implements BinaryTreeInfo {
	protected int size;
	protected Node<E> root;
	
	public int size() {
		return size;
	}
	
	public Node<E> getbstRoot() {
		return root;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public void clear() {
		root = null;
		size = 0;
	}
	
	public boolean contains(E element) {
		return false;
	}
	
	public boolean isComplete() {
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		boolean isleaf = false;
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (isleaf && !node.isLeaf()) return false;
			if (node.right != null) {
				queue.offer(node.right);
			}else if (node.right != null && node.left == null) {
				return false;
			}
			if (node.left != null) {
				queue.offer(node.left);
			}else {
				isleaf = true;
			}
 		}
		return true;
	}
	
	public int height() {
		int levelSize = 1;
		int height = 0;
		Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {
		  Node<E> node = queue.poll();
		  levelSize--;
		  if (node.left != null) {
			queue.offer(node.left);
		  }
		  if (node.right != null) {
			queue.offer(node.right);
		  }
		  if (levelSize == 0) {
			height ++;
			levelSize = queue.size();
		  }
		}
		return height;
	}
	
    public void preorderTraversal() {
		preorderTraversal(root);
	}
    
    public void preorderTraversal(Node<E> root) {
    	if (root == null) {
			return;
		}
    	ArrayList<E> list = new ArrayList<>();
    	Stack<Node<E>> stack = new Stack<>();
    	stack.push(root);
    	while (!stack.isEmpty()) {
			Node<E> node = stack.pop();
			list.add(node.element);
			System.out.println(node.element);
			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
	}
    
    public Node<E> invertTree() {
    	return invertTreeTraversal(root);
	}
    
    public Node<E> invertTreeTraversal(Node<E> root) {
    	if (root == null) {
			return null;
		}
    	Node<E> tmp = root.right;
    	root.right = root.left;
    	root.left = tmp;
		invertTreeTraversal(root.left);
		invertTreeTraversal(root.right);
		return root;
	}
	
	public static class Node<E> {
		public E element;
		public Node<E> left;
		public Node<E> right;
		public Node<E> parent;
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
	}
	
    public Node<E> predecessor(Node<E> node) {
    	if (node == null) {
			return null;
		}
    	Node<E> p = node.left;
    	if (p != null) {
			while (p.right != null) {
				p = p.right;
			}
			return p;
		}
    	while (node.parent != null && node == node.parent.left) {
			node = node.parent;
		}
    	return node.parent;
	}
    
    public Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}
		Node<E> p = node.left;
		if (p != null) {
			while (p.right != null) {
				p= p.right;
			}
			return p;
		}
		
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}
		
		return node.parent;
	}
    
//  public void inorderTraversal() {
//		inorderTraversal(root);
//	}
  
//  public void inorderTraversal(Node<E> node) {
//		if (node == null) {
//			return;
//		}
//		inorderTraversal(node.left);
//		System.out.println(node.element);
//		inorderTraversal(node.right);
//	}
  
//  public void postorderTraversal() {
//		postorderTraversal(root);
//	}
//  
//public void postorderTraversal(Node<E> node) {
//		if (node == null) {
//			return;
//		}
//		postorderTraversal(node.left);
//		postorderTraversal(node.right);
//		System.out.println(node.element);
//	}
  
  public void levelorderTraversal(Visitor<E> visitor) {
  	levelorderTraversal(root,visitor);
	}
  
  public void levelorderTraversal(Node<E> root,Visitor<E> visitor) {
  	Queue<Node<E>> queue = new LinkedList<>();
  	queue.offer(root);
  	while (!queue.isEmpty()) {
		  Node<E> node = queue.poll();
		  if (visitor.visit(node.element)) {
			  break;
		  }
		  if (node.left != null) {
			queue.offer(node.left);
		  }
		  if (node.right != null) {
			queue.offer(node.right);
		  }
		}
  }
      
  public void postorderTraversal() {
		postorderTraversal(root);
	}
  
  public void postorderTraversal(Node<E> node) {
		Stack<Node<E>>stack = new Stack<>();
		Node<E> curNode = node;
		Node<E> preNode = null;
		while (curNode != null || !stack.isEmpty()) {
			while (curNode != null) {
				stack.push(curNode);
				curNode = curNode.left;
			}
			curNode = stack.pop();
			if (curNode.right == null || curNode.right == preNode) {
				System.out.println(curNode.element);
				preNode = curNode;
				curNode = null;
			}else {
				stack.push(curNode);
				curNode = curNode.right;
			}
		}
  }
  
  
  public void inorderTraversal() {
		inorderTraversal1(root);
	}
  
  public void inorderTraversal(Node<E> node) {
		Stack<Node<E>> stack = new Stack<>();
		while (!stack.isEmpty() || node != null) {
			if (node != null) {
				stack.push(node);
				node = node.left;
			}else{
				Node<E> tmpNode = stack.pop();
				System.out.println(tmpNode.element);
				node = tmpNode.right;
			}
		}
  }
  
  public void inorderTraversal1(Node<E> root) {
		Stack<Node<E>> stack = new Stack<>();
      stack.push(root);
      root = root.left;
      while (!stack.isEmpty() || root != null) {
          if (root != null) {
              stack.push(root);
              root = root.left;
          }else {
              Node<E> node = stack.pop();
				System.out.println(node.element);
              root = node.right;
          }
      }
  }
  
  public List<List<E>> levelOrder() {
  	return levelOrder(root);
  }
  
  public List<List<E>> levelOrder(Node<E> root) {
      List<List<E>> ret = new ArrayList<List<E>>();
      if (root == null) {
          return ret;
      }
      Queue<Node<E>> queue = new LinkedList<Node<E>>();
      queue.offer(root);
      while (!queue.isEmpty()) {
          List<E> level = new ArrayList<E>();
          int currentLevelSize = queue.size();
          for (int i = 1; i <= currentLevelSize; ++i) {
              Node<E> node = queue.poll();
              level.add(node.element);
              if (node.left != null) {
                  queue.offer(node.left);
              }
              if (node.right != null) {
                  queue.offer(node.right);
              }
          }
          ret.add(level);
      }
      
      return ret;
  }
	
	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return root;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).left;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).right;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).element;
	}
}
